// 接雨水 

/**
 * @param {number[]} height
 * @return {number}
 */
// var trap = function (height) {
//   let result = 0
//   let len = height.length
//   for (let i = 1; i < len - 1; i++) {
//     let left = height[0], right = height[i + 1]
//     for (let j = 1; j <= i - 1; j++) {
//       left = Math.max(left, height[j])
//     }
//     for (let k = i + 1; k < len; k++) {
//       right = Math.max(right, height[k])
//     }

//     if (left > height[i] && right > height[i]) {
//       result += Math.min(left, right) - height[i]
//     }

//   }

//   return result
// };

// var trap = function (height) {
//   let result = 0
//   let len = height.length
//   let l_max = [], r_max = []
//   for (let i = 0; i < len; i++) {
//     l_max[i] = height[i]
//     r_max[i] = height[i]
//   }
//   for (let i = 1; i < len; i++) {
//     l_max[i] = Math.max(l_max[i - 1], height[i])
//   }
//   for (let j = len - 2; j >= 0; j--) {
//     r_max[j] = Math.max(r_max[j + 1], height[j])
//   }
//   for (let i = 1; i < len - 1; i++) {
//     result += Math.min(l_max[i], r_max[i]) - height[i]
//   }

//   return result
// };

// 单调栈
var trap = function (height) {
  let result = 0
  let len = height.length
  let st = []
  st.push(0)
  for (let i = 1; i < len; i++) {
    if (height[i] <= height[st[st.length - 1]]) {
      st.push(i)
    } else {
      while (st.length > 0 && height[i] > height[st[st.length - 1]]) {
        let mid = st.pop()
        if (st.length > 0) {
          let h = Math.min(height[i], height[st[st.length - 1]]) - height[mid]
          let w = i - st[st.length - 1] - 1
          result += h * w
        }
      }
      st.push(i)
    }
  }

  return result
};

console.log(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]));
